from bisect import bisect_left
from filecmp import cmp

from dht.bucket import KBucket
from dht.exception import BucketFull
from dht.utils import intify


class KTable(object):
    def __init__(self, nid):
        self.nid = nid
        self.buckets = [KBucket(0, 2**160)]
        self.sizes = 0

    def append(self, node):
        # global bucket
        index = self.bucket_index(node.nid)
        try:
            bucket = self.buckets[index]
            bucket.append(node)
            self.sizes += 1
            # print(self.sizes)
        except IndexError:
            print("Index error")
            return
        except BucketFull:
            if not bucket.in_range(self.nid):
                return
            else:
                self.split_bucket(index)
                self.append(node)

        # 返回与目标node ID或infohash的最近K个node.

        # 定位出与目标node ID或infohash所在的bucket, 如果该bucuck有K个节点, 返回.
        # 如果不够到K个节点的话, 把该bucket前面的bucket和该bucket后面的bucket加起来, 只返回前K个节点.
        # 还是不到K个话, 再重复这个动作. 要注意不要超出最小和最大索引范围.
        # 总之, 不管你用什么算法, 想尽办法找出最近的K个节点.

    def get_neighbors(self, target):
        nodes = []
        if len(self.buckets) == 0:
            return nodes
        if len(target) != 20:
            return nodes

        index = self.bucket_index(target)
        try:
            nodes = self.buckets[index].nodes
            min = index - 1
            max = index + 1

            while len(nodes) < 8 and ((min >= 0) or (max < len(self.buckets))):
                if min >= 0:
                    nodes.extend(self.buckets[min].nodes)

                if max < len(self.buckets):
                    nodes.extend(self.buckets[max].nodes)

                min -= 1
                max += 1

            num = intify(target)
            nodes.sort(lambda a, b, num=num: cmp(num ^ intify(a.nid), num ^ intify(b.nid)))
            return nodes[:8]  # K是个常量, K=8
        except IndexError:
            return nodes

    def bucket_index(self, target):
        # print(bisect_left(self.buckets, intify(target)))
        return bisect_left(self.buckets, intify(target))

    def split_bucket(self, index):
        old = self.buckets[index]
        mid = int((old.max - old.min) / 2)
        point = old.max - mid
        new = KBucket(point, old.max)
        old.max = point
        self.buckets.insert(index + 1, new)
        for node in old.nodes[:]:
            if new.in_range(node.nid):
                new.append(node)
                old.remove(node)

    def __iter__(self):
        for bucket in self.buckets:
            yield bucket